generating function

문제요약: 수열의 누적합의 누적합의 누적합의 i번째 원소를 구하는 쿼리 + 수열의 원소를 변경하는 쿼리.

오늘 처음으로 생성함수를 사용해 문제를 해결했다. 생성함수를 최근에 공부했기때문에 수열을 a, 그 생성함수를 $A(z)$라고 할때 그 누적합 생성함수는 $A(z)*1/(1-x)=A(z)\sum\limits_{i\geq0}{z^i}$인게 바로 떠올랐다. 이를통해 결과수열을 b, 그 생성함수를 B(z)라고 할때 $B(z) = A(z)(\sum\limits_{i\geq0}{z^i})^3 = A(z)\sum\limits_{i\geq0}{\frac{(i+2)(i+1)}{2}z^i}$까지 정리할 수 있었다. $A(z)=\sum\limits_{i\geq0}{a_iz^i}$이므로 다시쓰면 $\sum\limits_{i\geq0}{a_iz^i}\sum\limits_{i\geq0}{\frac{(i+2)(i+1)}{2}z^i}$이므로 a와 (i+2)*(i+1)/2의 컨볼루션을 fft로 구하고 그 결과를 업데이트해서 쓰는쪽으로 생각해봤지만, fft결과를 빠르게 업데이트할 방법을 몰라서 못풀었다. 검색좀 해보니 실제로도 업데이트가 있는 임의의 수열 a에 대해 컨볼루션을 sublinear하게 업데이트할 방법은 없는거같다.

대회 끝나고 더 생각해본 의식의 흐름은 아래와 같다. 처음에는 합성곱을 $B(z)=\sum\limits_{n\geq0}{\sum\limits_{0\leq{i}\leq{n}}{a_{n-i}\frac{(i+2)(i+1)}{2}}z^n}$ 이라고 적었다. (i+2)같은 상수가 있는 항에 n-i를 넣으면 더 지저분해보일까봐 무의식적으로 a의 인덱스로 n-i를 사용한것 같다. 그런데, Enumerative Combinatorics에 잠깐 언급되었듯이, 생성함수와 점화식은 인덱스를 어떻게 설정하냐에 따라 관찰의 난이도가 달라진다. 우리는 a가 임의의 수열이기 때문에, a가 최대한 간단하게 유지되는게 바람직하고, 따라서 아래와 같이 a의 인덱스로 i를 줘보자. $B(z)=\sum\limits_{n\geq0}{\sum\limits_{0\leq{i}\leq{n}}{a_i\frac{(n-i+2)(n-i+1)}{2}}z^n}$ 이제는 해설의 기여도가 어쩌구 저쩌구하는 말을 해석할 수 있다. $b_n$의 값에 $a_i$는 $\frac{(n-i+2)(n-i+1)}{2}$만큼 곱해서 더해진다는 말이다. 이제는 조금 더 정리할 수 있다. 안쪽의 i에대한 합을 정리하기 위해 식을 i에 대해 풀어보자. $$ B(z)=\sum\limits_{n\geq0}{\sum\limits_{0\leq{i}\leq{n}}{a_i\frac{(i-n-2)(i-n-1)}{2}}z^n}\\ =\sum\limits_{n\geq0}{\sum\limits_{0\leq{i}\leq{n}}{a_i\frac{i^2+i(-2n-3)+(n^2+3n+2)}{2}}z^n}\\ =\sum\limits_{n\geq0}{ \frac{ \sum\limits_{0\leq{i}\leq{n}}{a_ii^2} + (-2n-3)\sum\limits_{0\leq{i}\leq{n}}{a_ii} + (n^2+3n+2)\sum\limits_{0\leq{i}\leq{n}}{a_i}}{2} z^n} $$ 이제 안쪽 각각의 합은 i에만 연관된 prefix sum이므로 펜윅트리3개로 문제를 해결할 수 있게된다. 끝!